package org.huawei260.String;

import java.util.Scanner;

/**
 * @Auther: qingle
 * @Date: 2024/8/25-1:57
 * @Description:
 * 读取输入：使用 Scanner 读取主字符串 t 和子字符串 p。
 * KMP搜索：使用KMP算法在主字符串 t 中查找子字符串 p 的出现位置。
 * 计算LPS数组：计算子字符串 p 的LPS（最长前缀后缀）数组，用于在不匹配时确定下一步的匹配位置。
 * 输出结果：如果找到匹配的子字符串，输出第一个字符的下标；否则输出 "No"。
 * KMP算法的高效性，可以在O(n + m)的时间复杂度内解决问题，其中n是主字符串的长度，m是子字符串的长度。
 * @version: 1.0
 */
public class O0058_连续子串_KMP {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		String source = scanner.nextLine();
		String target = scanner.nextLine();
		scanner.close();

		int index = kmpSearch(source, target); // 使用KMP算法查找子字符串
		if (index != -1) {
			System.out.println(index + 1); // 输出子字符串第一个字符的下标，从1开始
		} else {
			System.out.println("No");
		}
	}

	private static int kmpSearch(String t, String p) {
		int[] lps = computeLPS(p); // 计算子字符串的LPS（最长前缀后缀）数组
		int i = 0; // 主字符串的索引
		int j = 0; // 子字符串的索引
		while (i < t.length()) {
			if (p.charAt(j) == t.charAt(i)) {
				i++;
				j++;
			}
			if (j == p.length()) {
				return i - j; // 找到匹配的子字符串，返回第一个字符的下标
			} else if (i < t.length() && p.charAt(j) != t.charAt(i)) {
				if (j != 0) {
					j = lps[j - 1]; // 使用LPS数组进行下一步匹配
				} else {
					i++;
				}
			}
		}
		return -1; // 未找到匹配的子字符串
	}

	private static int[] computeLPS(String p) {
		int[] lps = new int[p.length()];
		int len = 0; // lps的长度
		int i = 1;
		lps[0] = 0; // lps[0]总是0
		while (i < p.length()) {
			if (p.charAt(i) == p.charAt(len)) {
				len++;
				lps[i] = len;
				i++;
			} else {
				if (len != 0) {
					len = lps[len - 1];
				} else {
					lps[i] = 0;
					i++;
				}
			}
		}
		return lps;
	}
}
